#include <vector>
#include <set>
#include <cmath>
#include <algorithm>

struct Collider {
    int _id;
    float _worldMatrix_m12;
    float _worldMatrix_m13;
    int _pos_ver;
    float pre_node_x;
    float pre_node_y;
    std::vector<int> _indexes;
    bool _is_move;
    int tag;
    // 其他Collider相关成员变量和方法
};

struct QuadtreeNode {
    float x;
    float y;
    float width;
    float height;
    std::vector<Collider*> objects;
};

class Quadtree {
private:
    QuadtreeNode bounds;
    std::vector<QuadtreeNode> all_obj;
    std::vector<Collider*> temp_objs;
    bool _is_clear_cache;
    QuadtreeNode* parent_node;
    float sub_width;
    int widnum;
    int heighnum;
    float move_x;
    float move_y;
    float pre_move_x;
    float pre_move_y;

public:
    Quadtree(Collider* node, float width, float height) {
        this->parent_node = node;
        this->bounds.x = 0;
        this->bounds.y = 0;
        this->bounds.width = width;
        this->bounds.height = height;
        this->_is_clear_cache = true;
        split();
    }

    void split() {
        if (bounds.width <= 0 || bounds.height <= 0) {
            return;
        }
        if (bounds.width > bounds.height)
            sub_width = bounds.height / 4;
        else
            sub_width = bounds.width / 4;

        widnum = static_cast<int>(std::ceil(bounds.width / sub_width));
        heighnum = static_cast<int>(std::ceil(bounds.height / sub_width));

        for (int j = 0; j < heighnum; j++) {
            for (int i = 0; i < widnum; i++) {
                all_obj.push_back({i * sub_width, j * sub_width, sub_width, sub_width, {}});
            }
        }
        all_obj.push_back({-1, -1, sub_width, sub_width, {}});
    }

    std::vector<int> getIndex(Collider* collider) {
        std::vector<int> indexes;
        float x_Midpoint = collider->world.aabb.x + (collider->world.aabb.width / 2);
        float y_Midpoint = collider->world.aabb.y + (collider->world.aabb.height / 2);
        int _x = static_cast<int>(std::floor(x_Midpoint / sub_width));
        int _y = static_cast<int>(std::floor(y_Midpoint / sub_width));

        auto isOverlap = [](const QuadtreeNode& rect1, const QuadtreeNode& rect2) {
            float r1x = rect1.x + rect1.width;
            float r1y = rect1.y + rect1.height;
            float r2x = rect2.x + rect2.width;
            float r2y = rect2.y + rect2.height;
            return !(rect1.x > r2x || rect2.x > r1x || rect1.y > r2y || rect2.y > r1y);
        };

        if (collider->world.aabb.width < sub_width && collider->world.aabb.height < sub_width) {
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    int nx = _x + dx;
                    int ny = _y + dy;
                    if (nx < 0 || ny < 0 || nx >= widnum || ny >= heighnum) continue;
                    int n = nx + ny * widnum;
                    if (isOverlap(all_obj[n], collider->world.aabb)) {
                        indexes.push_back(n);
                    }
                }
            }
            if (indexes.empty() && (_x < 0 || _y < 0 || _x >= widnum || _y >= heighnum)) {
                indexes.push_back(all_obj.size() - 1);
            }
        } else {
            for (size_t n = 0; n < all_obj.size(); n++) {
                if (isOverlap(all_obj[n], collider->world.aabb)) {
                    indexes.push_back(n);
                }
            }
        }
        return indexes;
    }

    void update(Collider* collider) {
        if (!collider->_indexes.empty()) {
            std::vector<int> indexes = getIndex(collider);
            std::set<int> oldSet(collider->_indexes.begin(), collider->_indexes.end());
            std::set<int> newSet(indexes.begin(), indexes.end());

            for (int oldIndex : oldSet) {
                if (newSet.find(oldIndex) == newSet.end()) {
                    del(all_obj[oldIndex].objects, collider);
                }
            }

            for (int newIndex : newSet) {
                if (oldSet.find(newIndex) == oldSet.end()) {
                    all_obj[newIndex].objects.push_back(collider);
                }
            }

            collider->_indexes = indexes;
        } else {
            insert(collider);
        }
    }

    void insert(Collider* collider) {
        std::vector<int> indexes = getIndex(collider);
        for (int i = 0; i < indexes.size(); i++) {
            all_obj[indexes[i]].objects.push_back(collider);
        }
        collider->_indexes = indexes;
    }

    void del(std::vector<Collider*>& objects, Collider* collider) {
        for (size_t ii = 0; ii < objects.size(); ii++) {
            if (objects[ii] == collider) {
                objects[ii] = objects.back();
                objects.pop_back();
                break;
            }
        }
    }

    void remove(Collider* collider) {
        if (!collider->_indexes.empty()) {
            for (int jj = 0; jj < collider->_indexes.size(); jj++) {
                del(all_obj[collider->_indexes[jj]].objects, collider);
            }
            clear_cache();
        }
    }

    std::vector<std::vector<Collider*>> retrieveAll() {
        if (_is_clear_cache || temp_objs.empty()) {
            temp_objs.clear();
            for (size_t i = 0; i < all_obj.size(); i++) {
                if (!all_obj[i].objects.empty()) {
                    temp_objs.push_back(all_obj[i].objects);
                }
            }
            _is_clear_cache = false;
        }
        return temp_objs;
    }

    void clear_cache() {
        _is_clear_cache = true;
    }

    void update_rect() {
        pre_move_x = move_x;
        pre_move_y = move_y;
        move_x = parent_node->_worldMatrix_m12 + parent_node->width / 2;
        move_y = parent_node->_worldMatrix_m13 + parent_node->width / 2;
    }

    bool check_move(Collider* collider) {
        float o_x = collider->pre_node_x - pre_move_x;
        float o_y = collider->pre_node_y - pre_move_y;
        float c_x = collider->_worldMatrix_m12 - move_x;
        float c_y = collider->_worldMatrix_m13 - move_y;
        return !(o_x == c_x && o_y == c_y);
    }

    std::vector<Collider*> retrieve(Collider* collider) {
        std::vector<Collider*> returnObjects;
        if (!collider->_indexes.empty()) {
            for (int i = 0; i < collider->_indexes.size(); i++) {
                for (Collider* obj : all_obj[collider->_indexes[i]].objects) {
                    returnObjects.push_back(obj);
                }
            }
        }
        return returnObjects;
    }

    void clear() {
        all_obj.clear();
    }

    void draw_debug_line() {
        // 实现绘制调试线的逻辑
    }
};